Localization of nonbacktracking centrality on dense subgraphs of sparse networks.

The nonbacktracking matrix and the related nonbacktracking centrality (NBC) play a crucial role in models of percolation-type processes on networks, such as nonrecurrent epidemics. Here we study the localization of NBC in infinite sparse networks that contain an arbitrary finite subgraph. Assuming the local tree likeness of the enclosing network, and that branches emanating from the finite subgraph do not intersect at finite distances, we show that the largest eigenvalue of the nonbacktracking matrix of the composite network is equal to the highest of the two largest eigenvalues: that of the finite subgraph and of the enclosing network. In the localized state, when the largest eigenvalue of the subgraph is the highest of the two, we derive explicit expressions for the NBCs of nodes in the subgraph and other nodes in the network. In this state, nonbacktracking centrality is concentrated on the subgraph and its immediate neighborhood in the enclosing network. We obtain simple, exact formulas in the case where the enclosing network is uncorrelated. We find that the mean NBC decays exponentially around the finite subgraph, at a rate which is independent of the structure of the enclosing network, contrary to what was found for the localization of the principal eigenvector of the adjacency matrix. Numerical simulations confirm that our results provide good approximations even in moderately sized, loopy, real-world networks.

Approximating nonbacktracking centrality and localization phenomena in large networks.

Message-passing theories have proved to be invaluable tools in studying percolation, nonrecurrent epidemics, and similar dynamical processes on real-world networks. At the heart of the message-passing method is the nonbacktracking matrix, whose largest eigenvalue, the corresponding eigenvector, and the closely related nonbacktracking centrality play a central role in determining how the given dynamical model behaves. Here we propose a degree-class-based method to approximate these quantities using a smaller matrix related to the joint degree-degree distribution of neighboring nodes. Our findings suggest that in most networks, degree-degree correlations beyond nearest neighbor are actually not strong, and our first-order description already results in accurate estimates, particularly when message-passing itself is a good approximation to the original model in question, that is, when the number of short cycles in the network is sufficiently low. We show that localization of the nonbacktracking centrality is also captured well by our scheme, particularly in large networks. Our method provides an alternative to working with the full nonbacktracking matrix in very large networks where this may not be possible due to memory limitations.

Enhanced robustness of single-layer networks with redundant dependencies.

Dependency links in single-layer networks offer a convenient way of modeling nonlocal percolation effects in networked systems where certain pairs of nodes are only able to function together. We study the percolation properties of the weak variant of this model: Nodes with dependency neighbors may continue to function if at least one of their dependency neighbors is active. We show that this relaxation of the dependency rule allows for more robust structures and a rich variety of critical phenomena, as percolation is not determined strictly by finite dependency clusters. We study Erdos-Rényi and random scale-free networks with an underlying Erdos-Rényi network of dependency links. We identify a special "cusp" point above which the system is always stable, irrespective of the density of dependency links. We find continuous and discontinuous hybrid percolation transitions, separated by a tricritical point for Erdos-Rényi networks. For scale-free networks with a finite degree cutoff we observe the appearance of a critical point and corresponding double transitions in a certain range of the degree distribution exponent. We show that at a special point in the parameter space, where the critical point emerges, the giant viable cluster has the unusual critical singularity S-S_{c}∝(p-p_{c})^{1/4}. We study the robustness of networks where connectivity degrees and dependency degrees are correlated and find that scale-free networks are able to retain their high resilience for strong enough positive correlation, i.e., when hubs are protected by greater redundancy.

Choosing among alternative histories of a tree.

The structure of an evolving network contains information about its past. Extracting this information efficiently, however, is, in general, a difficult challenge. We formulate a fast and efficient method to estimate the most likely history of growing trees, based on exact results on root finding. We show that our linear-time algorithm produces the exact stepwise most probable history in a broad class of tree growth models. Our formulation is able to treat very large trees and therefore allows us to make reliable numerical observations regarding the possibility of root inference and history reconstruction in growing trees. We obtain the general formula 〈lnN〉≅NlnN-cN for the size dependence of the mean logarithmic number of possible histories of a given tree, a quantity that largely determines the reconstructability of tree histories. We also reveal an uncertainty principle: a relationship between the inferability of the root and that of the complete history, indicating that there is a tradeoff between the two tasks; the root and the complete history cannot both be inferred with high accuracy at the same time.

Sensitivity of directed networks to the addition and pruning of edges and vertices.

Directed networks have various topologically different extensive components, in contrast to a single giant component in undirected networks. We study the sensitivity (response) of the sizes of these extensive components in directed complex networks to the addition and pruning of edges and vertices. We introduce the susceptibility, which quantifies this sensitivity. We show that topologically different parts of a directed network have different sensitivity to the addition and pruning of edges and vertices and, therefore, they are characterized by different susceptibilities. These susceptibilities diverge at the critical point of the directed percolation transition, signaling the appearance (or disappearance) of the giant strongly connected component in the infinite size limit. We demonstrate this behavior in randomly damaged real and synthetic directed complex networks, such as the World Wide Web, Twitter, the Caenorhabditis elegans neural network, directed Erdos-Rényi graphs, and others. We reveal a nonmonotonic dependence of the sensitivity to random pruning of edges or vertices in the case of C. elegans and Twitter that manifests specific structural peculiarities of these networks. We propose the measurements of the susceptibilities during the addition or pruning of edges and vertices as a new method for studying structural peculiarities of directed networks.

Nonbacktracking expansion of finite graphs.

Message passing equations yield a sharp percolation transition in finite graphs, as an artifact of the locally treelike approximation. For an arbitrary finite, connected, undirected graph we construct an infinite tree having the same local structural properties as this finite graph, when observed by a nonbacktracking walker. Formally excluding the boundary, this infinite tree is a generalization of the Bethe lattice. We indicate an infinite, locally treelike, random network whose local structure is exactly given by this infinite tree. Message passing equations for various cooperative models on this construction are the same as for the original finite graph, but here they provide the exact solutions of the corresponding cooperative problems. These solutions are good approximations to observables for the models on the original graph when it is sufficiently large and not strongly correlated. We show how to express these solutions in the critical region in terms of the principal eigenvector components of the nonbacktracking matrix. As representative examples we formulate the problems of the random and optimal destruction of a connected graph in terms of our construction, the nonbacktracking expansion. We analyze the limitations and the accuracy of the message passing algorithms for different classes of networks and compare the complexity of the message passing calculations to that of direct numerical simulations. Notably, in a range of important cases, simulations turn out to be more efficient computationally than the message passing.

Mapping the Structure of Directed Networks: Beyond the Bow-Tie Diagram.

We reveal a hierarchical, multilayer organization of finite components-i.e., tendrils and tubes-around the giant connected components in directed networks and propose efficient algorithms allowing one to uncover the entire organization of key real-world directed networks, such as the World Wide Web, the neural network of Caenorhabditis elegans, and others. With increasing damage, the giant components decrease in size while the number and size of tendril layers increase, enhancing the susceptibility of the networks to damage.

Scale-free networks with exponent one.

A majority of studied models for scale-free networks have degree distributions with exponents greater than two. Real networks, however, can demonstrate essentially more heavy-tailed degree distributions. We explore two models of scale-free equilibrium networks that have the degree distribution exponent γ=1, P(q)∼q^{-γ}. Such degree distributions can be identified in empirical data only if the mean degree of a network is sufficiently high. Our models exploit a rewiring mechanism. They are local in the sense that no knowledge of the network structure, apart from the immediate neighborhood of the vertices, is required. These models generate uncorrelated networks in the infinite size limit, where they are solved explicitly. We investigate finite size effects by the use of simulations. We find that both models exhibit disassortative degree-degree correlations for finite network sizes. In addition, we observe a markedly degree-dependent clustering in the finite networks. We indicate a real-world network with a similar degree distribution.

Scaling laws for impact fragmentation of spherical solids.

We investigate the impact fragmentation of spherical solid bodies made of heterogeneous brittle materials by means of a discrete element model. Computer simulations are carried out for four different system sizes varying the impact velocity in a broad range. We perform a finite size scaling analysis to determine the critical exponents of the damage-fragmentation phase transition and deduce scaling relations in terms of radius R and impact velocity v(0). The scaling analysis demonstrates that the exponent of the power law distributed fragment mass does not depend on the impact velocity; the apparent change of the exponent predicted by recent simulations can be attributed to the shifting cutoff and to the existence of unbreakable discrete units. Our calculations reveal that the characteristic time scale of the breakup process has a power law dependence on the impact speed and on the distance from the critical speed in the damaged and fragmented states, respectively. The total amount of damage is found to have a similar behavior, which is substantially different from the logarithmic dependence on the impact velocity observed in two dimensions.

New universality class for the fragmentation of plastic materials.

We present an experimental and theoretical study of the fragmentation of polymeric materials by impacting polypropylene particles of spherical shape against a hard wall. Experiments reveal a power law mass distribution of fragments with an exponent close to 1.2, which is significantly different from the known exponents of three-dimensional bulk materials. A 3D discrete element model is introduced which reproduces both the large permanent deformation of the polymer during impact and the novel value of the mass distribution exponent. We demonstrate that the dominance of shear in the crack formation and the plastic response of the material are the key features which give rise to the emergence of the novel universality class of fragmentation phenomena.

NAADP receptors are present and functional in the heart.

Alongside the well-studied inositol 1,4,5 trisphosphate and ryanodine receptors, evidence is gathering that a new intracellular release mechanism, gated by the pyridine nucleotide nicotinic acid adenine dinucleotide phosphate (NAADP), is present in numerous organisms, ranging from plant to mammalian cells (reviewed in [1]). Most cells have been shown to express at least two Ca(2+)-release mechanisms controlled by different messengers, and this can lead to redundancy, convergence, or divergence of responses. One exception appears to be muscle and heart contractile tissues. Here, it is thought that the dominant intracellular channel is the ryanodine receptor, while IP(3) receptors are poorly expressed and their role appears to be negligible. We now report that NAADP receptors are functional and abundant in cardiac microsomes. NAADP binds specifically and with high affinity (130 pM and 4 nM) to two sites on cardiac microsomes and releases Ca(2+) with an apparent EC(50) of 323 +/- 14 nM. Furthermore, binding experiments show that this receptor displays both positive and negative cooperativity, a peculiarity unique among intracellular Ca(2+) channels. Therefore, we show that the heart possesses multiple mechanisms to increase the complexity of Ca(2+) signaling and that NAADP may be integral in the functioning of this organ.

Molecular targets for pharmacological cytoprotection.

Cell death is common to many pathological conditions. In the past two decades, research into the mechanism of cell death has characterized the cardinal features of apoptosis and necrosis, the two distinct forms of cell death. Studies using in vivo disease models have provided evidence that apoptosis is induced by an array of pathological stimuli. Thus, molecular components of the machinery of apoptosis are potential pharmacological targets. The mechanism of apoptosis can be dissected into: (i) the initiation and signaling phase, (ii) the signal amplification phase, and (iii) the execution phase. Reflecting on the diversity of apoptotic stimuli, the initiation and signaling phase utilizes a variety of molecules: free radicals, ions, plasma membrane receptors, members of the signaling kinase cascades, transcription factors, and signaling caspases. In most of the apoptotic scenarios, impairment of mitochondrial function is an early event. Dysfunctioning mitochondria release more free radicals and hydrolytic enzymes (proteases and nucleases), amplifying the primary death signal. In the final phase of apoptosis, executioner caspases are activated. Substrates of the executioner caspases include nucleases, members of the cellular repair apparatus, and cytoskeletal proteins. Partial proteolysis of these substrates leads to distinctive morphological and biochemical changes, the hallmarks of apoptosis. The first steps toward pharmacological utilization of specific modifiers of apoptosis have been promising. However, since the potential molecular targets of cytoprotective therapy play important roles in the maintenance of cellular homeostasis, specificity (diseased versus healthy tissue) of pharmacological modulation is the key to success.

Nicotinic acid adenine dinucleotide phosphate triggers Ca2+ release from brain microsomes.

Mobilization of Ca2+ from intracellular stores is an important mechanism for generating cytoplasmic Ca2+ signals [1]. Two families of intracellular Ca(2+)-release channels - the inositol-1,4, 5-trisphosphate (IP3) receptors and the ryanodine receptors (RyRs) - have been described in mammalian tissues [2]. Recently, nicotinic acid adenine dinucleotide phosphate (NAADP), a molecule derived from NADP+, has been shown to trigger Ca2+ release from intracellular stores in invertebrate eggs [3] [4] [5] [6] and pancreatic acinar cells [7]. The nature of NAADP-induced Ca2+ release is unknown but it is clearly distinct from the IP3- and cyclic ADP ribose (cADPR)-sensitive mechanisms in eggs (reviewed in [8] [9]). Furthermore, mammalian cells can synthesize and degrade NAADP, suggesting that NAADP-induced Ca2+ release may be widespread and thus contribute to the complexity of Ca2+ signalling [10] [11]. Here, we show for the first time that NAADP evokes Ca2+ release from rat brain microsomes by a mechanism that is distinct from those sensitive to IP3 or cADPR, and has a remarkably similar pharmacology to the action of NAADP in sea urchin eggs [12]. Membranes prepared from the same rat brain tissues are able to support the synthesis and degradation of NAADP. We therefore suggest that NAADP-mediated Ca2+ signalling could play an important role in neuronal Ca2+ signalling.